package com.zjsru.plan2025.oneday;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 *
 * @Author: cookLee
 * @Date: 2025-04-07
 */
public class CanPartition {

    /**
     * 主
     * \
     * 输入：nums = [1,5,11,5]
     * 输出：true
     * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
     * \
     * 输入：nums = [1,2,3,5]
     * 输出：false
     * 解释：数组不能分割成两个元素和相等的子集。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        CanPartition canPartition = new CanPartition();
        int[] nums = new int[]{1, 5, 11, 5};
        System.out.println(canPartition.canPartition(nums));
    }

    public boolean canPartition(int[] nums) {
        // 先排序,如果能被2整除，说明可以进行子数组的分割
        Arrays.sort(nums);
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int len = nums.length;
        int target = sum / 2;
        int[][] dp = new int[len][target + 1];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }
        return this.helper(len - 1, target, nums, dp);
    }

    private boolean helper(int len, int target, int[] nums, int[][] dp) {
        if (len < 0) {
            return target == 0;
        }
        //已处理的数据
        if (dp[len][target] != -1) {
            return dp[len][target] == 1;
        }
        //选择当前元素或不选择当前元素
        boolean res = target >= nums[len] && this.helper(len - 1, target - nums[len], nums, dp) || this.helper(len - 1, target, nums, dp);
        dp[len][target] = res ? 1 : 0;
        return res;
    }

}
